﻿//给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。
//返回符合要求的 最少分割次数 。
//
//输入：s = "aab"
//输出：1
//解释：只需一次分割就可将 s 分割成["aa", "b"] 这样两个回文子串。
//
//输入：s = "a"
//输出：0
//
//输入：s = "ab"
//输出：1
//
//提示：
//	1 <= s.length <= 2000
//	s 仅由小写英文字母组成

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<bool>> isPal(n,vector<bool>(n)); // 统计所有⼦串是否是回⽂串
        for (int i = n - 1; i >= 0; i--)
            for (int j = i; j < n; j++)
                isPal[i][j] = s[i] == s[j]? (i + 1 < j ? isPal[i + 1][j - 1] : true): false;
        vector<int> dp(n, INT_MAX);
        for (int i = 0; i < n; i++) {
            if (isPal[0][i])
                dp[i] = 0;
            else {
                for (int j = 1; j <= i; j++)
                    if (isPal[j][i])
                        dp[i] = min(dp[i], dp[j - 1] + 1);
            }
        }
        return dp[n - 1];
    }
};